1. Technical Field
The present invention relates to an improved method and system for allowing attached devices to access a computer bus. In particular, the present invention relates to an improved method and system for allowing attached devices to access a computer bus, where such access is granted based upon priority levels assigned to the attached devices. Yet still more particularly, the present invention relates to an improved method and system for allowing attached devices to access a computer bus, where such access is granted based upon priority levels assigned to the attached devices, but where such access is granted in such a fashion that lower priority requests are granted in a fair and consistent manner.
2. Description of the Related Art
The present invention is related to a more efficient way to utilize a computer data bus. A computer data bus generally consists of a set of hardware lines--wires--used for data transfer among the components of a computer system. A computer data bus is essentially a shared highway that connects different parts of the system-including the microprocessor, disk-drive controller, memory, and input/output ports and enables them to transfer information. Buses are characterized by the number of bits they can transfer at a single time (e.g., an 8-bit data bus transfers 8 bits of data in parallel at a time; a 16-bit data bus transfers 16 bits in parallel at a time). The bus is integral to internal data transfer. Bus (computer), Microsoft.RTM. Encarta.RTM. 96 Encyclopedia..COPYRGT. 1993-1995 Microsoft Corporation. All rights reserved.
A computer bus is an amalgam of different types of "pure" communication links. Accordingly, prior to discussing a computer data bus it is useful to first discuss generally data communications links.
There are three characteristics that distinguish various data communication links: topology, duplexity, and line discipline. The topology of a data link refers to the logical-physical arrangement of stations on a link (e.g., a point-to-point topology (only two stations on the link), or a multipoint topology (more than two stations on the link). The duplexity of a link refers to the direction and timing of signal flow (e.g., a half-duplex link is similar to a one-lane, two-way bridge, in that stations on a half-duplex link can transmit and receive, but not simultaneously; a full-duplex link is similar to a two-way, two-lane bridge in that two stations can simultaneously send and receive data to and from each other).
Line discipline refers to who can talk when: a station should only transmit when it knows the physical transmission path is clear and when it knows the receiver is prepared to receive. Line discipline varies dependent upon the topology and duplexity of a link (e.g. a half-duplex, multi-point link of bus topology will require more discipline than a full-duplex, point-to-point link). Line discipline usually has three distinct phases: establishment of access to a link; data transfer over the link; and termination of the logical link between transmitter and receiver, which includes relinquishment of access to the link.
A computer bus is an amalgam of the foregoing described "pure" communication links. The computer bus itself is a multi-point half-duplex link of bus topology. That is, a collection of devices all attached to the same transmission medium. Such link requires a great amount of line discipline, since only one device at a time can "transmit over the link." This line discipline for the computer bus is provided by a second data communications link: a point-to-point full-duplex link of hub topology. The following figure will make this more clear.
FIG. 1 illustrates a computer bus. Shown is computer bus 100 to which a number of devices (e.g., device 102, device 104, device 106, device 108, and device 110) are connected. As is illustrated, computer bus 100 is a half-duplex link of bus topology, so only one of the attached devices can be transmitting over the link (computer bus 100) at any one time. Thus, access to the link must be controlled (i.e., there must be some form of line discipline).
The line discipline is provided by a second data communications link of hub topology formed between the attached devices (e.g., device 102, device 104, device 106, device 108, and device 110) and link access control station 112. The second data communications link of hub topology is composed of multiple point-to-point component links. These component links connect the attached devices (e.g., device 102, device 104, device 106, device 108, and device 110) to link access control station 112 and, as is illustrated in FIG. 1, are full-duplex in that there is one line over which each device (e.g., device 102, device 104, device 106, etc.) can send a request for access to the computer data bus (denoted in FIG. 1 as the request bus access (REQ) lines), and in that there is another line over which link access control station 112 can reply to a requesting device that access to computer bus 100 has been granted (denoted in FIG. 1 as the bus access request granted (GNT) lines).
It is common to assign priorities to the differing devices connected to computer bus 100. For example, device 102 and device 106 could be assigned high priority, device 104 medium priority, and device 108 low priority. If link access control station 112 receives a request from high, medium, and low priority devices, then link access control station 112 allows bus access to the high priority devices first, the medium priority devices second, and the low priority devices last. Differing requests for access to computer bus 100 from devices with the same priority are generally granted in same prespecified order.
As an example of how a computer bus operates, assume device 102, device 106, and device 108 wish access to computer bus 100. Accordingly, device 102, device 106, and device 108 all activate and hold their respective request bus access (REQ) signals. Link access control station 112 notices that these respective request bus access (REQ) signals have been activated. In response, link access control station 112 prioritizes the requests dependent upon priorities previously assigned to the devices. Assume for the sake of illustration that device 106 has been assigned a highest priority, device 102 has been assigned a medium priority, and device 108 has been assigned a lowest priority. Accordingly, link access control station 112 determines that when computer bus 100 is free, device 106 (the highest priority requesting device) will be given access to computer bus 100.
When link access control station 112 determines that computer bus 100 is free, link access control station 112 activates and holds device 106's bus access request granted (GNT) signal. Device 106 now knows that it is free to transmit over computer bus 100. When link access control station 112 determines that the requesting device 106 should relinquish control of computer bus 100, link access control station 112 deactivates device 106's request granted signal (GNT), which tells device 106 that when it completes its current operation, it should no longer transmit over computer bus 100.
Subsequent to detecting that its bus access request granted (GNT) signal has been deactivated, device 106 completes any computer bus 100 transmission that it is currently engaged in and then deactivates its request bus access signal (REQ). Once link access control station 112 notes that device 106 has deactivated its request access signal, link access control station 112 knows computer bus 100 is free. Consequently, link access control station 112 issues another bus access request granted (GNT) signal to the highest priority device that is now requesting access to computer bus 100.
If no other devices are requesting access, device 102 (medium priority) will be granted access to the bus. However, if in the interim (i.e., while device 106 was accessing the bus) another highest priority device requested access, then link access control device 112 will grant access to that highest priority device and both device 102 (medium priority) and device 108 (lowest priority) will have to continue to wait.
The problem with the foregoing is that if link access control station 112 keeps receiving requests from highest priority devices, it is completely possible that requests from both the medium and the lowest priority devices could be completely starved out, or could be delayed for a great amount of time. It is clear that a need exists for a method and system which will allow the lower priority devices access to the bus.
However, any solution to such a need must recognize that the priority system exists for a reason: there are devices which need to be given priority access to computer bus 100. On the other hand, it is important that the lower priority requests to the bus be granted, because while these requests are lower in priority they are still essential for the overall functioning of the computing system utilizing computer bus 100.
In light of the foregoing it clear that a need exists for a method and system which will allow attached devices to access a computer bus, and where such access is granted based upon priorities assigned to the attached devices, but where such access is granted in such a fashion that lower priority requests are granted in a fair and consistent manner.